//给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 
//
// candidates 中的数字可以无限制重复被选取。 
//
// 说明： 
//
// 
// 所有数字（包括 target）都是正整数。 
// 解集不能包含重复的组合。 
// 
//
// 示例 1： 
//
// 输入：candidates = [2,3,6,7], target = 7,
//所求解集为：
//[
//  [7],
//  [2,2,3]
//]
// 
//
// 示例 2： 
//
// 输入：candidates = [2,3,5], target = 8,
//所求解集为：
//[
//  [2,2,2,2],
//  [2,3,3],
//  [3,5]
//] 
//
// 
//
// 提示： 
//
// 
// 1 <= candidates.length <= 30 
// 1 <= candidates[i] <= 200 
// candidate 中的每个元素都是独一无二的。 
// 1 <= target <= 500 
// 
// Related Topics 数组 回溯算法 
// 👍 836 👎 0

package leetcode.editor.cn;

import java.util.*;

//Java：组合总和
public class P39CombinationSum {

    /**
     *
     * 思路：动态规划，难点是怎么去重  网上的思路是回溯，但是回溯看不懂
     *
     * 执行用时： 21 ms , 在所有 Java 提交中击败了 6.54% 的用户 内存消耗： 40.7 MB , 在所有 Java 提交中击败了 5.04% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<List<Integer>> combinationSum(int[] candidates, int target) {
            Arrays.sort(candidates);
            if(candidates.length == 0 || target < candidates[0]){
                return new ArrayList<>();
            }

            List<List<Integer>>[] dp = new List[target + 1];

            // 初始化  candidates[0] 放本身
            List<List<Integer>> zeroList = new ArrayList<>();
            List<Integer> temp2List = new ArrayList<>();
            temp2List.add(candidates[0]);
            zeroList.add(temp2List);
            dp[candidates[0]] = zeroList;

            for (int i = candidates[0] + 1; i < target + 1; i++) {
                for (int k = 0; k < candidates.length; k++) {
                    // 如果 i 是在candidates中的，就把本身加进去
                    if (i == candidates[k]) {
                        List<Integer> self2List = new ArrayList<>();
                        self2List.add(candidates[k]);
                        dp[candidates[k]] = dp[candidates[k]] == null ? new ArrayList<>() : dp[candidates[k]];
                        dp[candidates[k]].add(self2List);
                    }else{
                        int sub = i - candidates[k];
                        if (sub < 0 || dp[sub] == null) {
                            continue;
                        }
                        dp[i] = dp[i] == null ? new ArrayList<>() : dp[i];
                        List<List<Integer>> tempList = copyList(dp[sub]);
                        for (List<Integer> aList : tempList) {
                            aList.add(candidates[k]);
                        }

                        removeSubNum(dp[i], candidates[k]);
                        dp[i].addAll(tempList);
                    }
                }
            }
            return dp[target] == null ? new ArrayList<>() : dp[target];
        }

        private void removeSubNum(List<List<Integer>> list, int num) {
            Iterator<List<Integer>> it = list.iterator();
            while (it.hasNext()) {
                List<Integer> tempList = it.next();
                if (tempList.contains(num)) {
                    it.remove();
                }
            }
        }

        // 拷贝，如果直接addAll 的话，改变list的话，会影响到前面的
        private List<List<Integer>> copyList(List<List<Integer>> sourceList) {
            List<List<Integer>> list = new ArrayList<>();
            for (List<Integer> tempList : sourceList) {
                List<Integer> numList = new ArrayList<>(tempList);
                list.add(numList);
            }
            return list;

        }
    }


    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P39CombinationSum().new Solution();
        int[] candidates = new int[]{2};
        solution.combinationSum(candidates, 1);
        // TO TEST
    }

}